package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class _169_MajorityElement {
    public static void main(String[] args) {
        Solution solution = new _169_MajorityElement().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 候选者投票法 (O(1) 空间复杂度)
    class Solution {
        public int majorityElement(int[] nums) {
            int cadidate = 0;
            int count = 0;
            for (int num : nums) {
                if (count == 0) {
                    cadidate = num;
                }
                if (num == cadidate) {
                    count++;
                } else {
                    count--;
                }
            }
            return cadidate;
        }
    }

    // 哈希表 (O(n) 空间复杂度)
    class Solution1 {
        public int majorityElement(int[] nums) {
            int n = nums.length;
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() > n / 2) {
                    return entry.getKey();
                }
            }
            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}